Route planning devices, such as those employing Global Positioning Systems (GPS) can be used to plan a route from one location to another. A* (“A star”) is a computer algorithm that is widely used in pathfinding and graph traversal, for plotting an efficiently traversable path between multiple points, called nodes. A* is an informed search algorithm, or a best-first search, meaning that it solves problems by searching among all possible paths to the solution (goal) for the one that incurs the smallest cost (least distance travelled, shortest time, etc.), and amoung these paths it first considers the ones that appear to lead most quickly to the solution. It is formulated in terms of weighted graphs: starting from a specific node of a graph, it constructs a tree of paths starting from that node, expanding paths one step at a time, until one of its paths ends at the predetermined goal node.
When route planning is restricted to roads, the limited options for travel (limited set of nodes) can allow A* to calculate a path, even a long path, in a span of time that is acceptable to a user. However, route planning via A* can be time intensive and occasionally too-slow for real-time routing, especially for off-road travel. When the potential areas for travel (nodes) are not restricted to roads (such as walking or off-road travel by recreational vehicles or otherwise), the increase in nodes can inundate A* to add significant time to that which is needed to arrive at the output path.
Still further, interpretation of A* instructions by a processor of a routing device causes specific operations within the routing device. The operations of A* proscribe that calculations made for one node have the potential to impact other nodes. Accordingly, nodes are usually processed in a serial, one-at-a-time fashion without the ability to consider calculations from multiple simultaneously processing sources/cores. Relatedly, A* instructions are not configured to allow massively parallel threading such as that employed in a GPU.
Accordingly, what is needed is a device and method for improving operation of routing devices and that is able to quickly and efficiently operate in the large node environment of off-road travel.